import java.util.HashMap;
import java.util.HashSet;

public class InOut {

	public HashMap<String, Double> s_rules;
	public HashMap<String, Double> t_rules;
	public String[] tags;
	public int tagsCount;
	public String[] words;
	public int wordsCount;
	public double[][][] inside;
	public double[][][] outside;
	public BackP[][][] back;
	public HashMap<String, Integer> tagIndex;
	public HashSet<String> stags;
	public HashSet<String> wordTypes;
	
	class BackP
	{
		int bidx;
		String rule;
	}
	
	public void prepare()
	{
		for (String s:s_rules.keySet())
			s_rules.put(s, Math.log(s_rules.get(s)));
		for (String s:t_rules.keySet())
			t_rules.put(s, Math.log(t_rules.get(s)));
		tagIndex = new HashMap<String, Integer>();
		for (int i=0; i<tags.length; i++)
			tagIndex.put(tags[i], i);
		stags = new HashSet<String> ();
		for (String s:s_rules.keySet())
		{
			String[] tokens = s.split("\\|");
			//if (tokens[1].indexOf(" ")>=0)
				stags.add(tokens[0]);
		}
	}
	
	public void initialize()
	{
		inside = new double[wordsCount+1][wordsCount+1][tagsCount];
		outside = new double[wordsCount+1][wordsCount+1][tagsCount];
		
		for (int i=0; i<=wordsCount; i++)
		{
			for (int j=0; j<=wordsCount; j++)
			{
				for (int k=0; k<tagsCount; k++)
				{
					inside[i][j][k] = Double.NEGATIVE_INFINITY;
					outside[i][j][k] = Double.NEGATIVE_INFINITY;
				}
			}
		}
		
		for (int i=0; i<wordsCount; i++)
		{
			for (int k=0; k<tagsCount; k++)
			{
				inside[i][i+1][k] = t_rules.get(tags[k]+"|"+words[i]);
			}
		}
	}
	
	public void inside()
	{
		for (int l=2; l<=wordsCount; l++)
		{
			for (int i=0; i<=wordsCount-l; i++)
			{
				int j=i+l;
				for (int k=i+1; k<=j-1; k++)
				{
					for (String s:s_rules.keySet())
					{
						String[] tokens = s.split("\\|");
						int index1 = tagIndex.get(tokens[0]);
						String[] tagsp = tokens[1].split(" ");
						int index2 = tagIndex.get(tagsp[0]);
						int index3 = tagIndex.get(tagsp[1]);
						inside[i][j][index1] = logplus(inside[i][j][index1], s_rules.get(s) + inside[i][k][index2] + inside[k][j][index3]);
					}
				}
			}
		}
	}
	
	public void outside()
	{
		outside[0][wordsCount][tagIndex.get("TOP")] = 0;
		for (int l=wordsCount; l>=2; l--)
		{
			for (int i=0; i<=wordsCount-l;i++)
			{
				int j=i+l;
				for (int k=i+1; k<=j-1;k++)
				{
					for (String s:s_rules.keySet())
					{
						String[] tokens = s.split("\\|");
						int index1 = tagIndex.get(tokens[0]);
						String[] tagsp = tokens[1].split(" ");
						int index2 = tagIndex.get(tagsp[0]);
						int index3 = tagIndex.get(tagsp[1]);
						outside[i][k][index2] = logplus(outside[i][k][index2], outside[i][j][index1] + s_rules.get(s) + inside[k][j][index3]);
						outside[k][j][index3] = logplus(outside[k][j][index3], outside[i][j][index1] + s_rules.get(s) + inside[i][k][index2]);
					}
				}
			}
		}
	}
	
	public double expectS(String rule)
	{
		double result = Double.NEGATIVE_INFINITY;
		
		String[] tokens = rule.split("\\|");
		int index1 = tagIndex.get(tokens[0]);
		String[] tagsp = tokens[1].split(" ");
		int index2 = tagIndex.get(tagsp[0]);
		int index3 = tagIndex.get(tagsp[1]);
		
		double fac = outside[0][wordsCount][tagIndex.get("TOP")];
		for (int l=2; l<=wordsCount; l++)
		{
			for (int i=0; i<=wordsCount-l; i++)
			{
				int j=i+l;
				for (int k=i+1; k<=j-1; k++)
				{
					result = logplus(result, outside[i][j][index1] + inside[i][k][index2] + inside[k][j][index3]);
				}
			}
		}
		result = result - fac;
		return result;
	}
	
	public double logplus(double logx, double logy)
	{
		if (logx==Double.NEGATIVE_INFINITY)
			return logy;
		else if (logy==Double.NEGATIVE_INFINITY)
			return logx;
		else if ((logx-logy) > 32.0)
			return logx;
		else if ((logy-logx) > 32.0)
			return logy;
		else if (logx > logy)
			return logx + Math.log(1.0 + Math.exp(logy - logx));
		else if (logy > logx)
			return logy + Math.log(1.0 + Math.exp(logx - logy));
		else
			return logx + Math.log(2.0);
	}
	
	
	
}
